\newcommand{\Amax}{A_{\mbox{\scriptsize max}}}
\newcommand{\Dmax}{D_{\mbox{\scriptsize max}}}
\newcommand{\emax}{e_{\mbox{\scriptsize max}}}
\newcommand{\umax}{U_{\mbox{\scriptsize max}}}
We used fixed point theorems to prove the existence of a personalized
equilibrium, and relaxing the problem to finding
$\epsilon$-approximate equilibria automatically moves us from a
continuous to a discrete world.  Here, we show that finding an
$\epsilon$-approximate equilibrium is in \PPAD.  This is not
surprising given that several discrete fixed point problems have been
shown to be in the class \PPAD.  Our proof uses the machinery already
established for proving that finding approximate Nash equilibrium in
$r$-player games is in \PPAD~\cite{DaskalakisGoldbergPapadimitriou08}.
The proof from \cite{DaskalakisGoldbergPapadimitriou08}[Section~3.2] will
apply to personalized equilibria as well, as long as we can define a
polynomial-time computable function $f(x)$ for $x \in \mathbb{R}^{n
  \cdot k}$ for a game with $k$ players, $n$ strategies per player,
which satisfies the conditions we enumerate below.  We need to
introduce some notation first.  For $p \in [k]$ and $i \in [n]$, we
denote by $x_p^i$ the $((p-1)n + i)$-th coordinate of $x$ (the amount
that player $p$ plays strategy $i$).  For player $p$, let $D_p$ denote
the set $\{(p-1)n + j: j \in [n]\}$; that is, the dimensions
corresponding to the strategies of $p$.  Then $x_p$ is the projection
of $x$ on $D_p$ and $x_{-p}$ is the projection of $x$ on $[nk] -
D_p$. The function $f(x)$ must satisfy the following requirements for
the proof to translate:
\begin{enumerate}
\item $\forall p$, $\sum_i f(x_p^i) = 1$ 
\item If $\| x - x' \|_{\infty} < \delta$, then $\| f(x) - f(x')
  \|_{\infty} < \umax 2^{\mbox{\scriptsize poly}(n,m,k)}\delta$, where $m$ is the number of edges and $\umax$ is the maximum payoff entry in the given instance.
\item If $\|f(x) - x\|_{\infty} < \epsilon_1$, then $x$ is an $\epsilon$-approximate personalized equilibrium. Here, we will use any $\epsilon_1 \leq \frac{\epsilon}{n \umax}$. In the proof from \cite{DaskalakisGoldbergPapadimitriou08}, $\epsilon_1$ only affects the number of nodes in the \eol\ graph.
\end{enumerate}

\newcommand{\opt}{{\mathcal O}}

We define $f(x)$ as follows: we set $f(x)_p$ to be the
lexicographically least best response to $x_{-p}$.  We now show that
$f$ satisfies the three conditions listed above.  The first condition
is immediate from the definition of $f(x)$.  For the second condition,
fix $x$, $x'$, and a player $p$.  Then $f(x)_p$ is obtained by solving
a best response linear program for player $p$ given the strategy
distribution $x_{-p}$ of the other players.  The LP, which we denote
by $\opt$ for this proof, is over the variables $f(x)^i_p$, for
strategy $i \in S_p$, and $w_p(e)$ for every edge $e$, and maximizes a
linear utility $u(f(x)_p,w_p)$ subject to linear constraints $B
\cdot (f(x)_p,w_p)^T \ge c$.  We note that every element of $B$ is
either $0$ or $1$ and every element of $c$ is either $0$, $1$, or a
coordinate of $x_{-p}$.  Similarly, $f(x')_p$ is an optimal solution
to an LP $\opt'$, which maximizes $u(f(x')^i_p,w'_p)$ subject to $B
\cdot (f(x)_p, w'_p)^T \ge c'$, where $c'$ is derived from $x'_{-p}$
in the same way as $c$ is derived from $x_{-p}$.

Let $U$ and $U'$ denote the optimal values of $\opt$ and $\opt'$.  We
first argue that if $\|x - x'\|_\infty \le \delta$, then $|U - U'| \le
m \umax (nk)! \delta$, where $m$ is the number of edges and $\umax$ is
the maximum payoff entry in the given game.  We note that $x$
satisfies the constraints of $\opt'$ to within $\delta$.  We also know
that $\opt'$ is feasible.  The number of variables and constraints in
both $\opt$ and $\opt'$ are $n+m$ and $nk + m +1$.  Therefore, by
Lemma~\ref{lem:Lipschitz}, there exists a point $y$ that satisfies the
constraints of $\opt'_p$ such that $\|y - x\|_\infty \le (nk)!
\delta$; here we use the fact that every entry in the constraint
matrix and vector of $\opt$ and $\opt'$ is at most $1$.  Thus, the
utility achieved by $y$ is at least $u(f(x)_p,w_p) - m\umax(nk)!
\delta$, yielding $U' \ge U - m\umax(nk)! \delta$.  Similarly, we have
$U \ge U' - m\umax(nk)! \delta$.  This gives the desired bound $|U -
U'| \le m\umax(nk)! \delta$.

\newcommand{\prog}{{\mathcal P}}

By definition, we have that $(f(x)_p,w_p)$ is the lexicographically
least element of the feasibility LP consisting of the constraints of
$\opt_p$ together with the constraint $u(f(x)_p,w_p) \ge U$.  Let us
call this LP $\prog$.  Similarly, $(f(x')_p,w'_p)$ is the
lexicographically least element of the feasibility LP $\prog'$
consisting of the constraints of $\opt'$ together with the constraint
$u(f(x')_p,w'_p) \ge U'$.  We note that $P$ and $P'$ have the same set
of variables and the same constraint matrix; that is, $P$ and $P'$ can
be written down as $Ax \ge b$ and $Ax \ge b'$ respectively.  Since
$\|x - x'\|_\infty \le \delta$ and $|U - U'| \le m\umax(nk)!\delta$,
we have $\|b - b'\|_\infty \le m\umax (nk)!\delta$.  We now apply
Corollary~\ref{cor:Lipschitz} to obtain that $\|f(x)_p -
f(x')_p\|_\infty$ is at most $\umax 2^{\mbox{\scriptsize
    poly}(n,m,k)}\delta$.

For the third condition, recall our definition of an $\epsilon$-approximate personalized equilibrium. We require: (3a) for every player $p$, 
$$1 - \epsilon \leq \sum_e w_p(e) \leq 1$$ 
(3b) for each player pair $p$ and $q$, and for each strategy $s$, 
$$\left| \sum_{e: s \in e} w_p(e) - \sum_{e: s \in e} w_q(e) \right| \leq \epsilon$$
 and (3c) for any best response weight assignment $w^*_p$ for any player $p$, 
$$\sum_{e} w_p^*(e) u_p(e) - \sum_{e} w_p(e) u_p(e) \leq \epsilon$$ 

(3a) is immediate, and we have $\sum_e w_e(p) = 1$. For (3b), recall that $y_p$ is the exact best response to $x_{-p}$. Therefore, for any player pair $p$ and $q$ and strategy $s$ of $q$, we could find a weight assignments $w$ on all edges $e$ (specifically, the weight assignments that made this a best response) such that $\sum_{e: s' \in e} w_p(e) = y_p^{s'}$ (for all $s'$, strategies of $p$), and $\sum_{e: s \in e} w_p(e) = x_q^s$. Since $w$ was a weight function for $y$, we also have $\sum_{e:s \in e} w_q(e) = y_q^s$. We are told that $|y^{*s}_q - x_q^s|$ is at most $\epsilon_1$, so we have $|\sum_{e: s \in e} w_p(e) - \sum_{e: s \in e} w_q(e)| \leq \epsilon_1$. 

Condition (3c): As above, we can define the weight function $w^*_p(e)$ that makes $y_p$ a best response against $x_{-p}$. Also define any weight assignment $w_p$ that gives (for all strategies $s$ of $p$) $\sum_{e: s \in e} w_p(e) = x_p^s$. For any strategy $s$ of $p$, we are told that $|y_p^s - x_p^s| < \epsilon_1$, so we can say for any strategy $s$ of $p$, $\sum_{e: s \in e} w^*_p(e) - \sum_{e:s \in e} w_p(e) < \epsilon_1 \Rightarrow \sum_{e: s \in e} w^*_p(e) u_p(e) - \sum_{e:s \in e} w_p(e) u_p(e) < \epsilon_1 \umax$.  This means $\sum_s |\sum_{e: s \in e} w^*_p(e) u_p(e) - \sum_{e:s \in e} w_p(e) u_p(e) | < n \epsilon_1 \umax$ if $n$ is the number of strategies for $p$. We can remove the absolute values because $w^*$ was a best response, giving $\sum_{e} w_p^*(e) u_p(e) - \sum_{e} w_p(e) u_p(e) \leq \epsilon$ as required, as long as $\epsilon_l \leq \epsilon \left( \frac{1}{n \umax }\right)$.